package 我的Java学习_算法基础.day_08;

/**
 * @author 挚爱之夕
 * @date 2021/8/24 - 08 - 24 - 11:15
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */

import java.util.Arrays;

/**
 * 限制重量下，求取得物品的最大价值，单个物品不可切割
 */
public class _131_背包问题 {
    public static void main(String[] args) {
//        int limit = 5; //限重
//        int t = maxValue1(0,limit);
//        System.out.println(t);
        int limit = 5; //限重
        memories = new int[4][limit+1];
        for (int i = 0; i < memories.length; i++) {//价值一定不为负
            Arrays.fill(memories[i],-1);
        }
        int t = maxValue1(0,limit);
        System.out.println(t);
    }
    static int[] weights = {2,1,3,2}; //质量数组
    static int[] values = {3,2,4,2};  //价值数组
    static int n = 4 ; //物品数量
    private static int maxValue(int index,int limit){
        if(limit<=0) return 0; //装不下了
        if(index>= weights.length) return 0; //没物品可选了
        //不拿
        int v2=maxValue(index+1,limit);
        //准备拿
        if(weights[index]>limit){ //装不下
            return v2;
        }else{ //装得下
            int v1= values[index]+ maxValue(index+1,limit- weights[index]);
            return Math.max(v1,v2);
        }
    }
    //记忆型递归
    static int[][] memories;//记录递归求解地值，可避免计算重复子问题

    /**
     *
     * @param index 从0开始
     * @param limit 限重
     * @return 限重下最大价值
     */
    private static int maxValue1(int index,int limit){
        if(limit<=0) return 0; //装不下了
        if(index>= weights.length) return 0; //没物品可选了
        //查询
        if(memories[index][limit]>=0){
            return memories[index][limit];
        }
        //不拿
        int v2=maxValue1(index+1,limit);
        //准备拿
        int ans;
        if(weights[index]>limit){ //装不下
            ans=v2;
        }else{ //装得下
            int v1= values[index]+ maxValue1(index+1,limit- weights[index]);
            ans=Math.max(v1,v2);
        }
        //记录
        memories[index][limit] = ans;
        return ans;
    }
}
